package a10_动态规划;

/**
 * <p>
 * a52_回文子串
 * </p>
 *
 * @author flyduck
 * @since 2025/3/5
 */
public class a52_回文子串 {
    public int countSubstrings(String s) {
        int result = 0;
        char[] chars = s.toCharArray();

        boolean[][] dp = new boolean[chars.length][chars.length];

        for (int i = chars.length -1 ; i >= 0; i--) {
            for (int j = i; j < chars.length; j++) {
                if(chars[i] == chars[j]){
                    if(j - i <= 1){
                        dp[i][j] = true;
                        result++;
                    }else if(dp[i+1][j-1] == true){
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
}

